package 剑指Offer._3140;

import general_class.TreeNode;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/9/29 22:21
 * 二叉搜索树与双向链表
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
 * 算法：深度优先搜素
 * 树的中序遍历
 */
public class _36 {

    TreeNode head, pre;
    public TreeNode treeToDoublyList(TreeNode root) {
        if (root == null) return root;
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }
    void dfs(TreeNode node) {
        if (node == null) return;
        dfs(node.left);
        if (pre == null) head = node;
        else pre.right = node;
        node.left = pre;
        pre = node;
        dfs(node.right);
    }

}
